package hash;

import java.util.HashMap;
import java.util.Map;

public class Solution_1 {

    /**
     * “一次遍历 + 哈希表，把找补数的问题变成 O(1) 查询。”
     * 具体拆解：
     * 1.
     * 创建哈希表  value → index ，边扫边存。
     * 2.
     * 对于当前元素  x ，计算补数  target - x 。
     * 3.
     * 若补数已存在于哈希表，立即返回这对下标；否则把当前元素及其下标存入哈希表继续向后扫描。
     * 4.
     * 遍历结束仍未找到则返回  [-1, -1] （题目保证有解时可省）
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}
